#include <stdlib.h>
#include <stdbool.h>
#include "stdio.h"
#include "time.h"
typedef long long ll;

/**
 * int:大约为10^9
 * longlong:约为10^18
 * */


//a的b次方对p取模的值 1<= a,b,p<= 10^9
int eg1(int a, int b, int p) {
    int ans = 1 % p;
    for (; b != 0; b >>= 1) {
        if ((b & 1) == 1) { ans = (int) (((long long) ans * a) % p); }
        a = (int) (((long long) a * a) % p);
    }
    return ans;
}
//a*b%p 1<=a,b,p<=10^8
long long eg2(int a,int b,int p){
    long long ans = 0;
    for(;b != 0;b >>= 1){
        if(b & 1 == 1){
            ans = (ans + a) % p;
        }
        a = a * 2 % p;
    }
    return ans;
}

long long eg2_ans2(ll a,ll b,ll p){
    a %= p, b %= p;
    long long c = (long double)a * b / p;
    long long ans = (a * b) - (c * p);
    if(ans < 0) ans += p;
    else if (ans >= p){ans -= p;}
    return ans;
}



int main(void) {
    srand(time(NULL));
    bool success = true;
    bool success2 = true;
    for (int i = 0; i <= 3; i++) {
        // 生成一个 [0, 1) 范围内的随机浮点数
        double float_a = (double) rand() / RAND_MAX;
        int a = (int) (float_a * 1000);
        double float_b = (double) rand() / RAND_MAX;
        int b = (int) (float_b * 1000);
        double float_p = (double) rand() / RAND_MAX;
        int p = (int) (float_p * 1000) + 1;
        int res = eg1(a,b,p);
        long long c = 1;
        for (int j = 0; j < b; j++) {
            c = (c * a) % p;
        }
        if(res != (int)c){
            success = false;
            printf("a:%d b:%d p:%d c:%d res:%d \n",a,b,p,c,res);
        }
        long long d = (a * b) % p;
        long long res2 = eg2(a,b,p);
        if(res2 != d){
            success2 = false;
            printf("a:%d b:%d p:%d c:%lld res:%lld \n",a,b,p,d,res2);
        }
    }
    if(!success){
        printf("OOPS!!!!");
    }
    if(!success2){
        printf("eg2 OOPS!!!!");
    }
}
